//
// Created by Symps on 2025/11/22.
//

#include <iostream>
#include <vector>
using namespace std;

void dfs(vector<int>& A, vector<int>& B, vector<int>& C, int n) {
    if (n == 1) {
        C.push_back(A.back());
        A.pop_back();
        return;
    }
    dfs(A, C, B, n - 1);
    C.push_back(A.back());
    A.pop_back();
    dfs(B, A, C, n - 1);
}

void hanota(vector<int>& A, vector<int>& B, vector<int>& C) {
    size_t n{A.size()};
    dfs(A, B, C, n);
}

void test1() {
    vector<int> A{
        3, 2, 1, 0
    };
    vector<int> B;
    vector<int> C;
    hanota(A, B, C);
    for (auto i : C) {
        cout << i << " ";
    }
    cout << endl;
}

struct ListNode {
    int val;
    ListNode* next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode* next) : val(x), next(next) {}
};

using Node = ListNode;

class Solution {
public:
    Node* mergeTwoLists(Node* list1, Node* list2) {
        Node* head = new Node(-1);
        _mergeTwoLists(head, list1, list2);
        return head->next;
    }

    void _mergeTwoLists(Node* tail, Node* curr1, Node* curr2) {
        if (curr1 == nullptr) {
            tail->next = curr2;
            return;
        }
        if (curr2 == nullptr) {
            tail->next = curr1;
            return;
        }
        if (curr1->val < curr2->val) {
            tail->next = curr1;
            tail = curr1;
            _mergeTwoLists(tail, curr1->next, curr2);
        } else {
            tail->next = curr2;
            tail = curr2;
            _mergeTwoLists(tail, curr1, curr2->next);
        }
    }
};

void test2() {
    using Node = ListNode;
    Node* l1 = new Node(1, new Node(2, new Node(4)));
    Node* l2 = new Node(1, new Node(3, new Node(4)));
    Solution().mergeTwoLists(l1, l2);
}

Node* _reverseList(Node* head) {
    if (head == nullptr || head->next == nullptr) {
        return head;
    }
    Node* tail = _reverseList(head->next);
    tail->next = head;
    head->next = nullptr;
    return head;
}

Node* reverseList(Node* head) {
    if (head == nullptr) {
        return nullptr;
    }
    Node* newHead = head;
    while (newHead->next != nullptr) {
        newHead = newHead->next;
    }
    _reverseList(head);
    return newHead;
}

void test3() {
    Node* list = new Node(1, new Node(2/*, new Node(3, new Node(4, new Node(5)))*/));
    list = reverseList(list);
    for (Node* curr = list; curr != nullptr; curr = curr->next) {
        cout << curr->val << " ";
    }
    cout << endl;
}

double myPow(double x, int n) {
    if (n == 0) {
        return 1;
    }
    if (n == 1) {
        return x;
    }

    double half = myPow(x, n / 2);
    return half * half * (n % 2 == 0 ? 1 : (n > 0 ? x : 1 / x));
}

void test4() {
    int x = 2;
    int n = -3;
    cout << myPow(x, n) << endl;
}

void test5() {
    bool a{};
    int b = a;
    cout << b << endl;
}

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};

class Solution1 {
public:
    using Node = TreeNode;
    int sumNumbers(Node* root) {
        int ret{};
        preorder(root, 0, ret);
        return ret;
    }

    void preorder(Node* root, int before, int& ret) {
        if (root == nullptr) {
            return;
        }

        int x{before * 10 + root->val};
        if (root->left == nullptr && root->right == nullptr) {
            ret += x;
        }

        preorder(root->left, x, ret);
        preorder(root->right, x, ret);
    }
};

void test6() {
    using Node = TreeNode;
    Node* root = new Node(1, new Node(2), new Node(3));
    cout << Solution1().sumNumbers(root) << endl;

    int a = -11;
    string str = to_string(a);
    cout << str << endl;
}

int maxCountOfRectangle(int width, int height) {
    if (width == 0 || height == 0) {
        return 0;
    }
    if (width == height) {
        return 1;
    }

    if (width < height) {
        swap(width, height);
    }
    return width / height + maxCountOfRectangle(width % height, height);
}

void test7() {
    cout << maxCountOfRectangle(5, 3) << endl;
    vector<int> arr;
    arr.emplace_back();
}

class Solution2 {
public:
    vector<vector<int>> ret;
    int n;

    void preorder(vector<int>& nums, vector<int>& path, vector<bool>& used) {
        if (path.size() == n) {
            ret.emplace_back(path);
            return;
        }

        for (int i{}; i < n; ++i) {
            if (used[i]) {
                continue;
            }
            path.emplace_back(nums[i]);
            used[i] = true;

            preorder(nums, path, used);

            path.pop_back();
            used[i] = false;
        }
    }

    vector<vector<int>> permute(vector<int>& nums) {
        ret.clear();
        n = nums.size();
        vector<int> path;
        vector<bool> used(n, false);
        preorder(nums, path, used);
        return ret;
    }
};

void test8() {
    vector<int> nums{1,2,3};
    Solution2 s;
    auto ret = s.permute(nums);
    for (auto i : ret) {
        for (auto j : i) {
            cout << j << " ";
        }
        cout << endl;
    }
    cout << endl;

    auto ret2 = s.permute(nums);
    for (auto i : ret2) {
        for (auto j : i) {
            cout << j << " ";
        }
        cout << endl;
    }
    cout << endl;
}

int main() {
    // test1();
    // test2();
    // test3();
    // test4();
    // test5();
    // test6();
    // test7();
    test8();
    return 0;
}
